#include<stdio.h>
#include<malloc.h>
#include<string.h>

//2.1 树结构体实现
#define NAMESIZE 20           //节点名称长度
typedef char NODE[NAMESIZE];  //节点名称类型NODE，存储节点名称

typedef struct BROTHERNODE   //兄弟节点类型，表示兄弟关系
{
    NODE node;               //兄弟节点名称
    struct BROTHERNODE *next;//兄弟节点链接指针，链接其他兄弟
}BROTHERNODE,*BROTHER;       //重命名兄弟节点类型,BROTHER为指向BROTHERNODE的指针

typedef struct PARENTNODE     //双亲节点类型，表示子树树根节点
{
    NODE node;                //双亲节点名称              
    BROTHER children;         //所有子节点
}PARENT;                      //重命名双亲节点类型，PARENT为PARENTNODE的代名

typedef struct TREENODE       //树分支节点类型
{
    PARENT node;              //双亲节点，表示子树的树根节点
    struct TREENODE *next;    //双亲节点指针指向其他双亲节点
}TREENODE,*TREE;              //重命名树分支节点类型，TREE为指向TREENODE的指针

//2.2 树存储实现
/*
//2.2.1 通用比较函数
int Equal(NODE n1,NODE n2, int *fun())
{
    return (int)fun(n1,n2);
}//判断树的两个节点是否相同，若相同则为1，否则则为0

//2.2.2 通用赋值函数
void Set (NODE n1,NODE n2,void *fun())
{
    fun(n1,n2);
}
*/

//2.2.3 兄弟节点关系的构建
BROTHER Add_A_Brother(BROTHER br,NODE node)        //Add_A_Brother把一个节点加入到兄弟节点群中
{
    BROTHER b,pb;                                  //兄弟节点
    b=(BROTHER)malloc(sizeof(struct BROTHERNODE)); //动态开辟一个兄弟节点
    //Set(b->node,node,node,SteValue);             //【下面两行是类型为str时的情况，其他类比】
    strcpy(b->node,node);
    b->next=NULL;
    if(br==NULL)                                    //没有兄弟节点的情况
    {
        br=b;                                       //node就是第一个兄弟
    }
    else                                            //有兄弟节点的情况
    {
        pb=br;                                      //node就是最后一个兄弟节点【值在b中，头插入】
        while(pb->next)   pb=pb->next;
        pb->next=b;
    }
    return br;                                      //返回兄弟节点【指针】
}

//2.2.4 双亲与子节点关系的构建
TREE Form_Pa_Ch(NODE pa,BROTHER br)                 //将兄弟节点(所有子节点)链接到双亲节点中，构成一个子树
{
    TREE parent;
    parent=(TREE)malloc(sizeof(struct TREENODE));   //创建双亲节点
    //Set(parent->node.node,pa,Setvalue)
    strcpy(parent->node.node,pa);
    parent->next=NULL;
    parent->node.children=br;                       //兄弟节点与双亲节点构成子树
    return parent;                                  //返回带兄弟节点的双亲结点，即子树
}

//2.2.5 将带子节点的双亲节点加入到树中
TREE Add_A_Sub_Tree(TREE tree,TREE subtree) //将双亲结点加入到树中
{
    TREE t=tree;                        //临时树
    if(tree==NULL)                      //树不存在
    {
        tree=subtree;                   //带子节点的双亲节点即为树
    }
    else                                //树存在
    {
        while(t->next)  t=t->next;
        t->next=subtree;                //带子节点的双亲节点加入到树的最后
    }
    return tree;                        //返回树指针
}//tree是链式队列，通过上述程序实现子树subtree(双亲结点)进队列过程

//2.2.6 清除兄弟节点和树
BROTHER ClearBrothers(BROTHER br)  //回收兄弟节点空间
{
    BROTHER br1=br;                //临时兄弟变量
    while(br)                      //【遍历兄弟节点】
    {
        br1=br;
        br=br->next;               //【挨个变量赋给临时指针】
        free(br1);                 //回收单元
        return br;
    }
    return br;                     //返回NULL
}

//2.2.7 清空树并回收数据单元
TREE ClearTree(TREE tree)
{
    TREE tree1=tree;              //临时树
    while(tree)                   //【遍历双亲节点】
    {
        tree1=tree;
        tree=tree->next;          //【挨个变量赋给临时指针】
        free(tree1);              //回收单元
    }
    return tree;
}//在程序运行结束前需要动态回收动态开辟的数据单元
//以上两个程序实际上是出队列过程，只是没有返回值

//2.2.8 字符数值转换
//把字符串的字符'/'转换为转义字符'\0'(字符串结束标志)，故需要在字符串数组中存放多个节点名称(兄弟节点)的字符串
void CreateStr(char *brotherset)  //字符数组转换为多个字符串
{
    char *c=brotherset;           //临时字符串
    while(*c)
    {
        if(*c=='/')  *c='\0';     //插入字符串结束标志
        c++;
    }
    c++;
    *c='\0';                      //多一个结束标记
}

//2.2.9 字符数组建立兄弟关系
//把字符串数组中的多个兄弟节点节点名称建立成树的兄弟节点群(链表)
BROTHER CreateBrothers(BROTHER brothers,char *brotherset)   //若干个节点构成兄弟
{
    char *p=brotherset;                                     //多个节点，分隔符'/'
    NODE node;
    CreateStr(brotherset);                                  //变成多个字符串
    while(*p)
    {
        //Set(Node,p,setvalue);
        strcpy(node,p);
        brothers=Add_A_Brother(brothers,node);              //加入兄弟关系中
        p+=strlen(node)+1;                                  //下一个节点
    }
    return brothers;                                        //返回兄弟节点链表
}

//2.2.10 根据树文件建立树
//树文件为txt文件，其记录格式为单数行为双亲节点，偶数行为子节点，用字符'/'分隔符分开
TREE CreateTree(TREE tree,char *filename)               //从文件创建树
{
    TREE subtree;
    BROTHER brothers;
    FILE *fp;
    char parent[200],brotherset[5000];
    fp=fopen(filename,"r");
    while(!feof(fp))                                     //文件中是否还存在树的节点名称
    {
        fscanf(fp,"%s",parent);                          //读入双亲节点
        fscanf(fp,"%s",brotherset);                      //读入若干兄弟节点(子节点)，分隔符'/'
        brothers=NULL;
        brothers=CreateBrothers(brothers,brotherset);    //构建双亲节点
        subtree=Form_Pa_Ch(parent,brothers);             //构建子树
        tree=Add_A_Sub_Tree(tree,subtree);                //树中加入子树
    }
    fclose(fp);                                          //关闭文件
    return tree;                                         //返回所建的树
}

//2.3 树搜索实现
//2.3.1 复制子节点集
//复制所有节点（链表），返回复制结果的头指针，建立链式队列
BROTHER CopyBrothers(BROTHER children)                       //节点集复制
{
    BROTHER copynode,lastnode,head=NULL;                     //没有子节点
    while(children)
    {
        copynode=(BROTHER)malloc(sizeof(struct BROTHERNODE));
        //Set(copynode->node,cildren->node,SetValue);
        strcpy(copynode->node,children->node);               //复制节点
        copynode->next=NULL;
        if(head==NULL)
        {
            head=copynode;                                   //第1个节点
        }
        else
        {
            lastnode->next=copynode;                         //非第1个节点：建立链接，复制子节点集
        }
        lastnode=copynode;
        children=children->next;                             //下一个子节点
    }
    return head;                                             //返回头节点指针
}

//2.3.2 扩展节点集
//根据树结构从双亲节点中找到所有孩子节点(兄弟节点)，并复制所有孩子节点，最后返回所有复制结果的头指针
BROTHER ExpandNodes(TREE tree,NODE pa)              //由节点获取所有子节点
{
    BROTHER children=NULL;                          //孩子节点
    TREE t=tree;                                    //树
    while(t)                                        //节点不为空
    {
        //if(Equal(t->node.node,pa,EqualFun)==0)
        if(strcmp(t->node.node,pa)==0)              //找到分支节点
        {
            children=CopyBrothers(t->node.children);
            break;
        }
        t=t->next;                                  //下一个双亲结点
    }
    return children;
}

//2.3.3 所有节点进栈
//将所有节点进栈并返回堆栈指针//
typedef struct BROTHERNODE *STACK;              //定义堆栈类型，实际上也是节点链表【兄弟节点链表】
STACK PushChildren(STACK stack,BROTHER children)//所有节点进栈
{
    BROTHER p,head;
    head=CopyBrothers(children);                //复制所有孩子节点
    p=head;                                     //复制节点并入堆栈
    if(p!=NULL)                                 //存在孩子节点
    {
        while(p->next)  p=p->next;              //指向最后节点
        p->next=stack;                          //链表连接
        stack=head;
    }
    return stack;
}

//2.3.4 出栈与回收堆栈
STACK Pop_A_Child(STACK stack,NODE child)  //出栈
{
    STACK p=stack;
    if(p!=NULL)                            //堆栈不为空
    {
        //Set(child,p->node,SetValue);
        strcpy(child,p->node);             //获取节点名称
        stack=p->next;                     //堆栈后移
        free(p);                           //回收节点单元
    }
    return stack;                          //返回堆栈头指针
}

STACK ClearStack(STACK stack)              //回收栈空间
{
    stack=(STACK)ClearBrothers((BROTHER)stack);   //清除所有节点，得到空指针
    return stack;                          //返回空指针
}

//2.3.5 可回溯、盲目、深度优先搜索
#define TRUE 1                              //定义符号常量“真”
#define FALSE 0                             //定义符号常量“假”
typedef int STATUS;                         //定义状态类型，表示“真”或“假”

//2.4 树求解路径实现
//2.4.1 路径与堆栈设计//
typedef struct BROTHERNODE *PATH;      //路径也采用链式存储，其与兄弟节点性质一样，形式相同
//对多个路径也采用链式存储，其存储结构描述如下
typedef struct PATHS                   //路径集合
{
    PATH path;
    struct PATHS *next;
}PATHS,*STACKPATHS;                    //路径栈【多条路径采用链式存储】

//2.4.2 节点加入路径
PATH Add_A_Node_To_Path(NODE node,PATH path)   //在路径中加入一个节点形成新的路径
{
    PATH p;
    p=(BROTHER)malloc(sizeof(struct BROTHERNODE));
    //Set(p->node,node,SetValue)
    strcpy(p->node,node);                     //等价，赋值
    if(path==NULL)                            //第1个节点
    {
        p->next=NULL;
    }
    else                                      //非第1个节点
    {
        p->next=path;                         //加入到路径头部
    }
    path=p;                                   //路径倒序加入
    return path;                              //返回路径头部
}

//2.4.3 复制路径与路径集合
PATH CopyPath(PATH path)                         //复制一条路径，返回新路径
{
    PATH tempath;
    tempath=(PATH)CopyBrothers((BROTHER)path);   //路径与兄弟节点集合相同、
    return tempath;
}

PATHS* CopyPaths(struct PATHS *paths)            //复制路径集合
{
    PATHS *copynode,*lastnode,*head=NULL;
    while(paths)                                 //路径集合不为空
    {
        copynode=(PATHS *)malloc(sizeof(PATHS)); //路径节点
        copynode->path=CopyPath(paths->path);    //复制一条路径
        copynode->next=NULL;                     //复制路径初始化
        if(head==NULL)                           //第1条路径
        {
            head=copynode;
        }
        else                                     //非第1条路径
        {
            lastnode->next=copynode;
        }
        lastnode=copynode;                        //加入路径集合
        paths=paths->next;
    }
    return head;
}

//2.4.4 路径倒序与显示
void RevPath(PATH path)                     //路径倒序，按树根倒目标节点的顺序
{
    int num=0,i;
    NODE *nodes;
    PATH p=path;
    while(p)                                //统计路径节点的个数
    {
        p=p->next;
        num++;
    }
    nodes=(NODE *)malloc(num*sizeof(NODE)); //开辟一维数组
    for(i=0,p=path;p;p=p->next,i++)         //读取路径节点置于数组中
    {
        //Set(nodes[i],p->node,SetValue);
        strcpy(nodes[i],p->node);
    }
    for(i=num-1,p=path;p;p=p->next,i--)     //数组数据倒序置于路径中
    {
        //Set(p->node,nodes[i],SetValue);
        strcpy(p->node,nodes[i]);
    }
    free(nodes);                            //回收数组空间
}

void PriPath(PATH path)                     //显示路径
{
    while(path!=NULL)
    {
        if(path->next->node!=NULL)  printf("%s->",path->node);
        else                        printf("%s",path->node);
        path=path->next;
    }
    printf("\n");
    //priBrothers((BROTHER)path);             //路径与兄弟节点集合形式相同
}

//2.4.5 路径加入路径集合
PATHS* Add_A_Path_To_Paths(PATH path,PATHS* paths)//路径加入到路径集合中
{
    PATH copypath;
    PATHS *ps=NULL,*p;
    if(path==NULL)   return paths;                //没有路径
    copypath=CopyPath(path);                      //复制路径
    ps=(PATHS *)malloc(sizeof(PATHS));            //开辟路径集合节点
    ps->path=copypath;                            //复制的路径置入
    ps->next=NULL;
    if(paths==NULL)                               //路径集合为空
    {
        paths=ps;
    }
    else                                          //路径集合为非空，新路径节点放置最后
    {
        p=paths;
        while(p->next) p=p->next;
        p->next=ps;
    }
    return paths;
}

//2.4.6 节点集合与路径形成路径集合
PATHS* FormPathsFromNodes(BROTHER brothers,PATH path,PATHS* paths)
//将每个节点均加入到路径中形成一条路径，最终形成多条路径
{
    PATH tempath;
    while(brothers)                                         //存在节点
    {
        tempath=CopyPath(path);                             //复制路径
        tempath=Add_A_Node_To_Path(brothers->node,tempath); //节点加入路径
        paths=Add_A_Path_To_Paths(tempath,paths);           //新路径加入路径集合
        brothers=brothers->next;                            //下一个节点
    }
    return paths;                                           //返回路径集合
}

//2.4.7 回收路径和路径集合空间
PATH ClearPath(PATH path)                     //回收路径空间，复用了回收兄弟节点的数据空间函数
{
    path=(PATH)ClearBrothers((BROTHER)path);  //路径与兄弟节点集合形式相同
    return path;
}
PATHS* ClearPaths(PATHS* paths)               //回收路径集合空间
{
    PATHS *paths1=paths;
    while(paths)                              //所有路径
    {
        paths1=paths;
        ClearPath(paths1->path);              //回收一条路径空间
        paths=paths->next;                    //下一条路径
        free(paths1);
    }
    return paths;
}

//2.4.8 路径进栈与所有路径进栈
STACKPATHS Push_A_Path(STACKPATHS stack,PATH path)     //一条路径进栈，把1条路径压入堆栈，返回堆栈头指针
{
    PATH tempath;
    STACKPATHS st;
    tempath=CopyPath(path);                            //复制节点
    st=(PATHS *)malloc(sizeof(PATHS));                 //路径节点
    st->path=tempath;                                  //置路径于栈中
    if(stack==NULL)                                    //第1条路径
    {
        st->next=stack;
    }
    else                                               //非第1条路径，已有路径
    {
        st->next=stack;
    }
    stack=st;
    return stack;
}

STACKPATHS PushPaths(STACKPATHS stack,PATHS *paths)  //所有路径进栈，把路径集合压入堆栈中，返回路径集合的头指针
{
    PATHS *p,*head;
    head=CopyPaths(paths);                           //复制路径集合
    p=head;
    if(p!=NULL)                                      //逐一加入栈中
    {
        while(p->next) p=p->next;
        p->next=stack;
        stack=head;
    }
    return stack;
}

//2.4.9 出栈与节点
STACKPATHS Pop_A_Node(STACKPATHS stack,NODE node,PATH *path)  //出栈，从堆栈中弹出获取路径和路径的节点名称，并返回堆栈头指针
{
    STACKPATHS p=stack;
    PATH tempath;
    if(p!=NULL)
    {
        tempath=p->path;                                //一条路径
        //Set(node,tempath->node,SetValue);
        strcpy(node,tempath->node);                     //获取节点
        *path=CopyPath(tempath);                        //获取路径
        stack=p->next;                                  //栈顶变化
        free(p);                                        //删除路径 
    }
    return stack;                                       //返回栈顶
}

//2.4.10 回收栈顶
STACKPATHS ClearStackPATHS(STACKPATHS stack)          //回收堆栈数据空间，复用了路径集合回收函数
{
    stack=(STACKPATHS)ClearPaths((PATHS *)stack);  //堆栈与路径的集合形式相同，复用函数              
    return stack;
}

//2.5 树搜索（递归）
//2.5.1 定位子树位置
TREE GetSubTree(TREE tree,NODE pa)                      //由结点获取所有子结点
{
    TREE subtree=tree;
    while(subtree)                                      //从树存储结构中遍历每颗子树
    {
        if(strcmp(subtree->node.node,pa)==0)  break;    //找到子树
        //if(Equal(subtree->node.node,pa)==0) break;
        else subtree=subtree->next;                     //下一棵子树
    }
    return subtree;                                     //返回子树
}

//2.6 树路径求解（递归）
//2.6.1 基于递归的子树路径搜索
STATUS SearchSubTreeRep(TREE tree,TREE subtree,NODE end,PATH *path)     //判断节点是否在树中，深度优先搜索，生成路径
{
    TREE subsubtree;                                                 //子树的子树（树根）
    BROTHER children;                                                //所有子节点
    STATUS flag=FALSE;                                               //是否从子树的子树中搜索到目标标识
    if(subtree==NULL)                                                //子树为空树
    {
        *path=NULL;                                                  //路径不存在
        return flag;
    }
    if(strcmp(subtree->node.node,end)==0)                            //子树树根就是目标
    //if(Equal(subtree->node.node,end,EqualFun)==0)
    {
        flag=TRUE;
        //*path=Add_A_Node_To_Path(children->node,*path);//【修复代码：中间路径重复输出】
    }
    else
    {
        children=subtree->node.children;                              //所有子节点
        while (children)                                              //依次遍历所有子节点
        {
            subsubtree=GetSubTree(tree,children->node);               //子节点的子树
            flag=SearchSubTreeRep(tree,subsubtree,end,path);          //搜索子树的子树
            if(flag==TRUE)                                            //子树的子树目标存在
            {
                *path=Add_A_Node_To_Path(children->node,*path);       //子节点加入路径
                break;                                                //找到目标，无需再找
            }
            children=children->next;                                  //搜索其他子节点
        }
    }
    return flag;                                                      //目标节点的存在性
}

//2.6.2 基于递归的完整路径求解
STATUS SearchPathRe(TREE tree,NODE start,NODE end,PATH* path)
{
    TREE subtree;                                                    //子树的树根
    STATUS flag=FALSE;                                               //目标是否存在标识
    subtree=GetSubTree(tree,start);                                  //子树（树根） 
    if(subtree)  flag=SearchSubTreeRep(tree,subtree,end,path);          //搜索路径
    return flag;                                                     //路径的存在性
}

//2.6.M 树路径求解（递归）部分主程序
//void PathsolveRecurrence()
int main()
{
    TREE tree=NULL;                                                 //链式存储结构树
    STACK stack=NULL;                                               //路径堆栈
    NODE start,end;                                                 //树开始节点名称和目标节点名称
    PATH path=NULL;                                                 //求得的路径
    STATUS flag;                                                    //是否求得路径的标识
    char *filename="D:\\Develop\\C-Main\\DS_LiGuohe\\Chapter2.txt"; //树数据文件
    tree=CreateTree(tree,filename);                                 //创建链式存储结构树
    printf("The Start Node:");
    scanf("%s",start);                                              //输入子树根节点名
    printf("The End Node:");
    scanf("%s",end);                                                //输入目标节点名称
    flag=SearchPathRe(tree,start,end,&path);                        //节点start到节点end的路径
    if(flag==1) path=Add_A_Node_To_Path(start,path);                //【修复代码：没有头节点start的问题】
    printf("Search %s from %s,Status=%d\n",end,start,flag);
    printf("Path=");
    //RevPath(path);                                                 //路径倒序
    //【修复代码：递归的为正序输出，无需路径倒序】
    PriPath(path);                                                   //显示路径
    printf("===============\n");
    ClearPath(path);
    ClearTree(tree);                                                //清空树结构空间
}